package com.zhuhao.sort;

import java.util.Arrays;

/**
 * 堆排序：https://www.cnblogs.com/chengxiao/p/6129630.html
 * <p>
 * 第一步构建大顶堆：
 * 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
 * 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
 * <p>
 * 第二步顶堆元素与末尾元素交换，排除末尾元素
 * <p>
 * 第三步继续第一步
 *
 * @Author zhuhao
 * @Date 2021/8/19 0019 10:34
 * @desc
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {5, 9, 6, 0, 1, 2, 4, 7, 3, 55, 12, 66, 97, 23, 20, 24};
        heapSort(arr, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr, int length) {
        //构建大顶堆
        for (int i = length / 2 - 1; i >= 0; i--) {
            //非叶子子节点：arr.length / 2 - 1
            //从第一个非叶子结点从下至上，从右至左调整结构
            if (arr[2 * i + 1] > arr[i]) {
                swap(arr, i, 2 * i + 1);
            }
            if (arr[2 * i + 2] > arr[i]) {
                swap(arr, i, 2 * i + 2);
            }
        }
        if (length == 0) {
            return;
        }

        swap(arr, 0, length);
        heapSort(arr, --length);
    }

    private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}
